#!/usr/bin/env python
# -*- coding: utf-8 -*-
import re

# provided with a list of dictionaries and a list of keys by which they shall be nested
def nest_dictionary_list(dictionary_list, *keys):
    nested_list = nest_dictionary_list_for_key(dictionary_list, keys[0])
    
    for i in range(len(nested_list)):
        nest = nested_list[i]
        if len(keys) > 1:
            nested_list[i] = (nest[0], nest_dictionary_list(nest[1], *keys[1:]))
    
    return nested_list
            
# In: list which is ordered by the key
def nest_dictionary_list_for_key(dictionary_list, key):
    last_value=dictionary_list[0][key]
    nest_list=[]
    cur_nest=[]
    for dictionary in dictionary_list:
        temp_dictionary = dictionary.copy()
        cur_value = temp_dictionary.pop(key)
        if cur_value == last_value:
            cur_nest.append(temp_dictionary)
        else:
            nest_list.append((last_value, cur_nest))
            cur_nest = []
            cur_nest.append(temp_dictionary)
            last_value = cur_value
            
    nest_list.append((last_value, cur_nest))
            
    return nest_list

def natural_key(string_):
    """See http://www.codinghorror.com/blog/archives/001018.html"""
    return [int(s) if s.isdigit() else s for s in re.split(r'(\d+)', string_)]

def natsort(list_, element_selector):
    """
    Sorts stuff humanly: Blatt 2 < Blatt 10
    """
    list_.sort(key = lambda x: natural_key(element_selector(x)))
    return list_